package algorithm.binary_tree;

import java.util.LinkedList;

public class BinaryTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    // 如何把二叉树的所有节点中的值加1
    void plusOne(TreeNode root) {
        if (root == null) {
            return;
        }
        plusOne(root.left);
        plusOne(root.right);
    }

    // 判断两颗二叉树是否相同
    boolean isSameTree(TreeNode root1, TreeNode root2) {
        // 都为空，显然相同
        if (root1 == null && root2 == null) {
            return true;
        }
        // 一个为空，一个非空，显然不同
        if (root1 == null || root2 == null) {
            return false;
        }
        // 两个都非空，但val不一样也不行
        if (root1.val != root2.val) {
            return false;
        }
        return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
    }

    // 二叉树遍历分为：递归遍历：前序遍历，中序遍历，后序遍历；迭代方式：层级遍历

    /*前序遍历*/
    void traverse(TreeNode root){
        if (root == null){
            return;
        }
        // 前序遍历代码
        traverse(root.left);
        traverse(root.right);
    }

    // 将二叉树打平成一个字符串中
    String SEP = ",";
    String NULL = "#";
    StringBuilder sb = new StringBuilder();

    void traverse(TreeNode root, StringBuilder sb){
        if (root == null){
            sb.append(NULL).append(SEP);
            return;
        }

        /*前序遍历位置*/
        sb.append(root.val).append(SEP);

        traverse(root.left, sb);
        traverse(root.right, sb);

    }

    /*将二叉树序列化为字符串*/
    String serialize(TreeNode root){
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    void serialize(TreeNode root, StringBuilder sb){
        if (root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // 反序列化，正常前中后序遍历的两种才能还原二叉树

    TreeNode deserialize(String data){
        // 将字符串转化为列表
        LinkedList<String> nodes = new LinkedList<>();
        for(String s:data.split(SEP)){
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    TreeNode deserialize(LinkedList<String> nodes){
        if (nodes.isEmpty()){
            return null;
        }

        // 前序遍历位置
        // 列表最左侧就是根节点
        String first = nodes.removeFirst();
        if (first.equals(NULL)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}
